package test2;

/**
 * @Author Jun jie Yi
 * 2022/4/12 20:24
 */
public class Test5 {
    public static void main(String[] args) {

        int[] arr = {1, 2, 3, 4, 5};
        int i = numOfSubarrays(arr);
        System.out.println(i);

    }

    public static int numOfSubarrays(int[] arr) {
        int mod = 1000000007;
        // dp[i]表示右边界为dp[i]的子数组中奇数和的数量
        int[] odd = new int[arr.length];
        int[] even = new int[arr.length];
        odd[0] = (arr[0] & 1) == 1 ? 1 : 0;
        even[0] = (arr[0] & 1) == 0 ? 1 : 0;
        for (int i = 1; i < arr.length; i++) {
            if ((arr[i] & 1) == 1) {
                // 奇
                // 单个数
                odd[i]++;
                odd[i] += even[i - 1];
                even[i] += odd[i - 1];
            } else {
                // 偶
                even[i]++;
                odd[i] += odd[i - 1];
                even[i] += even[i - 1];
            }
        }
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            count = (count + odd[i]) % mod;
        }
        return count;
    }
}
